// https://www.lintcode.com/problem/search-insert-position/my-submissions

class Solution {
public:
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: An integer
     */
     
    // int searchInsert(vector<int> &A, int target) {
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         if (A[i] >= target)
    //         {
    //             return i;
    //         }
    //     }
    //     return A.size();
    // } 
    
    
    // 法二：二分法
    // find first position >= target
    int searchInsert(vector<int> &A, int target) {
        if (A.empty())
        {
            return 0;
        }
        int start = 0; 
        int end = A.size() - 1;
        while (start + 1 < end)
        {
            int mid = (end - start) / 2 + start;
            if (A[mid] >= target)
            {
                end = mid;
            } else
            {
                start = mid;
            }
        }
        
        if (A[start] >= target)
        {
            return start;
        }
        if (A[end] >= target)
        {
            return end;
        }    
        return A.size();
    }
};